
# 跳跃游戏II：https://leetcode-cn.com/problems/jump-game-ii/submissions/
# 和括号生成是同样的思路，利用的是 抽象思想，树形结构解题

# 1.bfs
import collections
class Solution:
    def jump(self, nums):
        n = len(nums)
        queue = collections.deque()
        queue.append(0)
        def bfs():
            """ 深度优先遍历 """
            step = 1
            while queue:
                for i in range(len(queue)):
                    a = queue.popleft()
                    b = nums[a]
                    for j in range(b):
                        if a+j+1 == n - 1:
                            return step
                        if a+j+1 < n:
                            queue.append(a+j+1)
                step += 1

            return 0            

        return bfs()

# m = [8,2,4,4,4,9,5,2,5,8,8,0,8,6,9]
m = [3,5,1,2,9,1,1,1,1,4]

s = Solution()
print(s.jump(m))

'''
# 2.dfs
class Solution:
    def jump(self, nums):
        n = len(nums)
        step_min = float('inf')
        def dfs(cur_index, step):
            if cur_index == n-1:
                nonlocal step_min
                step_min = step if step < step_min else step_min
                return      

            a = nums[cur_index]           
            for i in range(a):
                if cur_index + i + 1 < n:
                    dfs(cur_index + i + 1, step + 1)

        dfs(0, 0)
        return step_min
'''

'''
class Solution:
    def jump(self, nums: List[int]) -> int:
        """ 贪心策略解题 """
        """
        n 长度
        step 步长
        left ，right  当前位置元素能到达的第一个元素和最后一个元素
        cur 当前位置的元素
        """
        n = len(nums)
        step = 0
        left, right, cur = 0, 0, 0

        # 1. 当元素个数为1 直接返回
        if len(nums) == 1:
            return 0

        # 2. 循环
        while left < n:
            # 1. 每次更新当前元素的 left， right
            left = right + 1
            right = cur + nums[cur]

            # 4. 如果 right 值大于 n-1了，说明下一步一定能到，返回
            if right >= n-1:
                return step + 1

            # 2. 根据贪心算法，找到能走的最远的 下一个元素
            temp = 0
            for i in range(left, right+1):
                if i + nums[i] > temp:
                    temp = i + nums[i]
                    cur = i

            # 3. 步数加一
            step += 1
'''